import sys
def input():
return sys.stdin.readline().rstrip("\r\n")
def maps():
return [int(i) for i in input().split()]
for _ in range(int(input())):
n, x = maps()
a = maps()
ok, cur_sum, max_sum = True, 0, 0
end_idx = n - 1
for i in range(n):
if a[i] < 0:
ok = False
cur_sum += a[i]
if cur_sum > max_sum:
max_sum = cur_sum
end_idx = i
elif cur_sum < 0:
cur_sum = 0
if ok:
print(*[max_sum + i * x for i in range(n + 1)])
else:
lzy = [-float("inf")] * (n + 1)
for i in range(n):
cur_sum = 0
for j in range(i, n):
cur_sum += a[j]
lzy[j - i + 1] = max(lzy[j - i + 1], cur_sum)
res = []
for k in range(n + 1):
bst = 0
for i in range(n + 1):
bst = max(
bst, lzy[i] + min(i, k) * x
) res.append(bst)
print(" ".join(map(str, res)))
#include <bits/stdc++.h>
using namespace std;
template<typename T> using vt = vector<T>;
using ll = long long;
using ld = long double;
using vi = vt<int>;
using ii = pair<int, int>;
using vii = vt<ii>;
template<typename T> using mipq = priority_queue<T, vt<T>,
greater<T>>;
template<typename T> using mapq = priority_queue<T>;
#define sqr(x) ((x)*(x))
#define debug(x) cerr << #x << " -> " << (x) << '\n'
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int) (x).size()
#define F first
#define S second
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int inf = 1e9 + 7;
const ll infll = 1e18 + 3;
ll fgcd(ll a, ll b) {while(b) swap(b, a %= b); return a;}
ll fpow(ll a, ll b, const ll c) {
ll ans = 1; a %= c;
for(; b; b >>= 1, a = a * a % c) if(b & 1) ans = ans * a % c;
return ans;
}
ll fpow(ll a, ll b) {
ll ans = 1;
for(; b; b >>= 1, a *= a) if(b & 1) ans *= a;
return ans;
}
int flog(int x) {return 31 - __builtin_clz(x);}
int flog(ll x) {return 63 - __builtin_clzll(x);}
void setIO(string name = "") {
cin.tie(0)->sync_with_stdio(0);
if (fopen((name+".in").c_str(), "r")) {
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}
const int N = 5e3 + 10;
int a[N], dp[N];
int n, t, x;
signed main() {
setIO("");
// freopen("milkvisits.in", "r", stdin);
// freopen("milkvisits.out", "w", stdout);
cin >> t;
while (t--) {
cin >> n >> x;
for (int i = 1; i <= n; i++) cin >> a[i], dp[i] = -inf;
for (int i = 1; i <= n; i++) {
int sum = 0;
for (int j = i; j <= n; j++) {
sum += a[j];
dp[j - i + 1] = max(dp[j - i + 1], sum);
}
}
for (int k = 0; k <= n; k++) {
int mx = 0;
for (int i = 1; i <= n; i++) {
mx = max(mx, dp[i] + x * min(i, k));
}
cout << mx << " \n"[k == n];
}
}
}
1673A - Subtle Substring Subtraction | 1345A - Puzzle Pieces |
711A - Bus to Udayland | 779B - Weird Rounding |
1703D - Double Strings | 1704C - Virus |
63A - Sinking Ship | 1704B - Luke is a Foodie |
298B - Sail | 239A - Two Bags of Potatoes |
1704E - Count Seconds | 682A - Alyona and Numbers |
44A - Indian Summer | 1133C - Balanced Team |
1704A - Two 0-1 Sequences | 1467A - Wizard of Orz |
1714E - Add Modulo 10 | 1714A - Everyone Loves to Sleep |
764A - Taymyr is calling you | 1714B - Remove Prefix |
1264F - Beautiful Fibonacci Problem | 52A - 123-sequence |
1543A - Exciting Bets | 1714D - Color with Occurrences |
215B - Olympic Medal | 1445A - Array Rearrangment |
1351A - A+B (Trial Problem) | 935B - Fafa and the Gates |
1291A - Even But Not Even | 1269A - Equation |